1. Field of the Invention
The present invention relates to the field of data compression and decompression.
2. Description of the Prior Art
Graphics and video systems generate large amounts of data. This data is typically stored in 16 to 32 bit per pixel in external SDRAM and is accessed at a high rate. For an HD screen resolution of 1920×1080 and a display rate of 60 HZ, data traffic volumes of 237 to 475 MBytes/s are required. A range of different data compression methods have been devised to reduce this traffic.
Many of these data compression methods look at the probability of occurrence of various values and encode the most probable values with a short code and the less probable values with a longer code. This is called variable length encoding. The measure for attainable compression is expressed by Shannon's entropy or Shannon's information function:
                    H        =                  -                                    ∑              n                        ⁢                                          Pr                ⁡                                  (                                      A                    n                                    )                                            ·                                                log                  2                                ⁡                                  (                                      Pr                    ⁡                                          (                                              A                        n                                            )                                                        )                                                                                        (        1        )            
Equation (1) shows that good compression can be obtained for data with a narrow probability density function such as that shown in FIG. 1a. 
If however the probability density functions is wide, such as is shown in FIG. 1b, equation (1) shows that less compression is possible, or when the symbol distribution is bimodal (see FIG. 1c) then a feasible algorithm for the compression of data is not so straightforward and does not have the same advantages.
This problem has been addressed previously by applying a filtering function to the input data signal to reduce the entropy, thereby making the variable length coding more advantageous. Previous techniques have focussed on this filtering stage in order to minimise the entropy to the lowest possible levels and have applied complex calculations to find both an appropriate filter for a particular region of an image and have applied different filtering techniques for different regions. Schemes that apply different filters to different data regions are referred to as context adaptive schemes, the schemes adapting to the different contexts by applying different filtering techniques. Note that despite the computational effort the filtering does not provide compression per-se, it just forms a residual signal which allows for the application of a simple variable length code optimised for narrow distributions as depicted in FIG. 1a. 
These techniques have been computationally costly, often requiring multiple passes over the data and intensive filtering of the local neighbourhood of the current symbol to determine the context. They therefore often require complex state-machines and controllers that are very specific to the source they are designed for. Furthermore, by paying little attention to the suitability of the actual variable length coder, they often result in sub-optimal bit allocation for all data sets of which the residual signal after filtering does not match the probability density function implied by the actual variable length coder.
It would be desirable to be able to compress data in a simple manner which is not overly sensitive to this symbol statistics mismatch
Moreover in the case that multiple variable length codes match to different probability density functions like those depicted in FIG. 1b and FIG. 1c, it would be desirable to have the ability to determine and realise the variable length code that implies the best matching probability density function, but without the complexity of context selection and adaptation required for the filter selection and adaptation.